//设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。 
//
// 实现 MinStack 类: 
//
// 
// MinStack() 初始化堆栈对象。 
// void push(int val) 将元素val推入堆栈。 
// void pop() 删除堆栈顶部的元素。 
// int top() 获取堆栈顶部的元素。 
// int getMin() 获取堆栈中的最小元素。 
// 
//
// 
//
// 示例 1: 
//
// 
//输入：
//["MinStack","push","push","push","getMin","pop","top","getMin"]
//[[],[-2],[0],[-3],[],[],[],[]]
//
//输出：
//[null,null,null,null,-3,null,0,-2]
//
//解释：
//MinStack minStack = new MinStack();
//minStack.push(-2);
//minStack.push(0);
//minStack.push(-3);
//minStack.getMin();   --> 返回 -3.
//minStack.pop();
//minStack.top();      --> 返回 0.
//minStack.getMin();   --> 返回 -2.
// 
//
// 
//
// 提示： 
//
// 
// -2³¹ <= val <= 2³¹ - 1 
// pop、top 和 getMin 操作总是在 非空栈 上调用 
// push, pop, top, and getMin最多被调用 3 * 10⁴ 次 
// 
//
// Related Topics 栈 设计 👍 1480 👎 0

package leetcode.editor.cn;

import java.util.Stack;

//Java：最小栈
public class P155MinStack {
	public static void main(String[] args) {
//
		MinStack minStack = new MinStack();
		minStack.push(-2);
		minStack.push(0);
		minStack.push(-3);
		System.out.println(minStack.getMin());; //--> 返回 -3.
		minStack.pop();
		System.out.println(minStack.top());; //--> 返回 0.
		System.out.println(minStack.getMin());;
		// TO TEST
	}

	//leetcode submit region begin(Prohibit modification and deletion)
	static class MinStack {

		private Stack<Long> stack;
		private long minVal;

		public MinStack() {
			stack = new Stack<>();
		}

		public void push(int val) {
			if (stack.empty()) {
				stack.push(0L);
				minVal = val;
			} else {
				stack.push((long)(val - minVal));
				minVal = Math.min(minVal, val);
			}
		}

		public void pop() {
			Long pop = stack.pop();
			if (pop < 0) {
				minVal = minVal - pop;
			}
		}

		public int top() {
			if (stack.peek() < 0) {
				return (int)minVal;
			} else {
				return (int)(stack.peek() + minVal);
			}
		}

		public int getMin() {
			return (int)minVal;
		}
	}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */
//leetcode submit region end(Prohibit modification and deletion)

}
